#include "DY.h"
#include <cmath>

Dy::Dy():size(0),capacity(10)
{
    array = new ElementType[capacity];
}

Dy::Dy(const Dy &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for(int i = 0;i < size;i++)
        array[i] = a.array[i];
}

Dy &Dy::operator=(const Dy &a)
{
    delete []array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for(int i = 0;i < size;i++)
        array[i] = a.array[i];

}

Dy::~Dy()
{
    delete []array;
}

void Dy::InsertTail(const ElementType &element)
{
    if(size == capacity)
        ReSize(capacity*2);
    array[size++] = element;
}

void Dy::InsertHead(const ElementType &element)
{
    if(size == capacity)
        ReSize(capacity*2);
    for(int i = size;i > 0;i--)
        array[i] = array[i-1];
    array[0] = element;
    size++;
}

void Dy::InserByIndex(const ElementType &element, size_t index)
{
    if(index >= capacity)
        return;
    if(size == capacity)
        ReSize(capacity*2);
    for(int i = size;i > index;i--)
        array[i] = array[i-1];
    array[index] = element;
    size++;

}

void Dy::RemoveByIndex(size_t index)
{
    if(index >= capacity)
        return;
    for(int i = index;i < size;i++)
        array[i] = array[i+1];
    size--;
}

void Dy::RemoveByElement(const ElementType &element)
{
    for(int i = 0;i < size;i++)
    {
        if(array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

ElementType *Dy::FindByIndex(size_t index)
{
    if(index >= size)
        return nullptr;
    return &array[index];
}

Dy Dy::FindByElement(const ElementType &element)
{
    Dy result;
    for(int i = 0;i < size;i++)
    {
        if(array[i] == element)
        {
            result.InsertHead((ElementType)i);
        }
    }
    return result;
}

void Dy::UpdateByIndex(size_t index, const ElementType &newvalue)
{
    if(index >= size)
        return;
    array[index] = newvalue;

}

void Dy::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    for(int i = 0;i < size;i++)
    {
        if(array[i] == oldvalue)
        {
            array[i] = newvalue;
        }
    }
}

Dy Dy::Merge(const Dy &a)
{
    Dy result;
    int first = 0;
    int second = 0;
    while(first < this->size && second < a.size)
    {
            if(array[first] < a.array[second])
            {
                result.InsertTail(array[first++]);
            }
            else
            {
                result.InsertTail(a.array[second++]);
            }
    }
    while(first < this->size)
        result.InsertTail(array[first++]);  
    while( second < a.size)
        result.InsertTail(a.array[second++]);    
    return result;
}

void Dy::Sort()
{
    FastSort(0,size-1,0,2*log(size));
}

void Dy::Duplicate()
{
    for(int i = 1;i < size;i++)
    {
        if(array[i] == array[i-1])
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

Dy Dy::FdIntrSctn(const Dy &a)
{
    Dy result;
    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first]);
            first++;
            second++;
        }
        else if(array[first] < a.array[second])
        {
            first++;
        }
        else
        {
            second++;
        }
    }
    return result;
}

Dy Dy::FindUnionSet(const Dy &a)
{
    Dy result;
    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first]);
            first++;
            second++;
        }
        else if(array[first] < a.array[second])
        {
            result.InsertTail(array[first]);
            first++;
        }
        else
        {
            result.InsertTail(array[second]);
            second++;
        }
    }
    while(first < size)
        result.InsertTail(array[first++]);
     while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

Dy Dy::FindDifference(const Dy &a)
{
        Dy result;
    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            first++;
            second++;
        }
        else if(array[first] < a.array[second])
        {
            result.InsertTail(array[first]);
            first++;
        }
        else
        {
            result.InsertTail(array[second]);
            second++;
        }
    }
    while(first < size)
        result.InsertTail(array[first++]);
     while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

bool Dy::operator==(const Dy &a)
{
    if(size != a.size)
        return false;
    for(int i = 0;i < size;i++)
    {
        if(array[i] != a.array[i])
            return false;
    }
    return true;
}

size_t Dy::BinarySearch(const ElementType &element)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        int mid = left +(right - left)/2;
        if(array[mid] = element)
            return mid;
        else if(array[mid] > element)
        {
            if(mid == 0)
                return -1;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

bool Dy::Contains(const Dy &a)
{
   int j = 0;
   for(int i = 0;i < size;i++)
   {
        if(array[i] == a.array[j])
            j++;
   }
   return j == a.size;
}

bool Dy::ContnsContains(const Dy &a)
{
    for(int i = 0;i < size - a.size;i++)
    {
        if(SubSquence(i,a.size) == a)
        {
            return true;
        }
    }
    return false;
}

Dy Dy::SubSquence(size_t index, size_t len)
{
    Dy result;
    if(index + len > size)
        return result;
    for(int i = index;i < index + len;i++)
        result.InsertTail(array[i]);
    return result;
}

void Dy::show()
{
}

size_t Dy::partition(size_t start, size_t end)
{
    int left = start;
    int right = end;
    ElementType temp = array[start];
    while(left < right)
    {
        while(array[right] < temp && left < right)
            right--;
        if(left < right)
            array[left++] = array[right];
        while(array[left] > temp && left < right)
            left++;
        if(left < right)
            array[right--] = array[left]; 
    }
    array[left] = temp;
    return left;
}

void Dy::FastSort(size_t start, size_t end, size_t CurDepth, size_t MaxDepth)
{
    if(start >= end)
        return;
    if(CurDepth < MaxDepth)
    {
        int par = partition(start,end);
        if(par != 0)
            FastSort(start,par -1 ,CurDepth + 1,MaxDepth);
        FastSort(par + 1,end,CurDepth,MaxDepth);
    }
    else
    {
        InsertSort(start,end);
    }
}

void Dy::InsertSort(size_t start, size_t end)
{
    for(int i = start + 1;i <= end;i++)
    {
        int j = i;
        ElementType temp = array[j];
        for(;j > 0;j--)
        {
            if(array[j-1] > temp)
                array[j] = array[j-1];
        }
        array[j] = temp;
    }
}

void Dy::ReSize(size_t capacity)
{
    this->capacity = capacity;
    size = size > capacity ? capacity : size;
    ElementType *newptr = new ElementType[capacity];
    for(int i = 0;i < size;i++)
        newptr[i] = array[i];
    delete []array;
    array = newptr;
}
